class sorting
{
	public static void quicksort(int [] list, int start, int end) 
	{
		if(start > end) return;
		int pivot = list[(start + end) / 2];
		int a = start ;
		int b = end ;
		int temp = 0 ;
		
		while(a <= b)
		{
			while(list[a] < pivot)
				a++ ;
			while(list[b] > pivot)
				b-- ;
			if(a <= b)
			{
				temp = list[a] ;
				list[a] = list[b] ;
				list[b] = temp ;
				a++ ;
				b-- ;
			}
		}
		if(start < a-1)
			quicksort(list, start, a-1 ) ;
		if(a < end)
			quicksort(list, a, end ) ;
	}

	public static int [] insertionsort(int [] list) 
	{
		int item ;
		int i ;
		int j ;
		for(i = 1 ; i < list.length; i ++)
		{
			item = list[i] ;
			for(j = i ; j > 0 && list[j-1]>(item) ; j--)
			{
				list[j] = list[j-1] ;
			}
			list[j] = item ;
		}
		return list ;
	}
	
	public int bs(int[] a, int s, int t) {
        int lo = s;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (t < a[mid]) hi = mid - 1;
            else if (t > a[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    }
}